package 动态规划;
/**
 * 传入一个数组，数字乱序存储正整数，右两个选手A，B，AB已知数组中元素的大小和位置，求AB获胜者的分数
 * 规则：
 * A先手B后手，只能从数组的最左边或者最右边拿分数，一次只能拿一张
 */
public class 最大分数 {
    public static void main(String[] args) {
        int[] arr = {30,100,50,20};
        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));
    }
//********************************动规优化******************************************************************

    public static int win3(int[] arr){
        int N = arr.length;
        //1.创建状态容器
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        //2.初始化状态容器
        for (int i = 0; i < N; i++) {
            fmap[i][i] = arr[i];
            gmap[i][i] = 0;
        }
        //3.状态转换方程
        //将列设置循环的条件，因为，由创建的表可知，列存在这越界的情况，而行不会越界
        for (int startCol = 1; startCol < N ; startCol++){
            int col = startCol;
            int row = 0;
            while (col < N){
                fmap[row][col] = Math.max((arr[row] + gmap[row+1][col]),(arr[col]+gmap[row][col-1]));
                gmap[row][col] = Math.min(fmap[row][col-1],fmap[row+1][col]);
                col++;
                row++;
            }
        }
        return  Math.max(fmap[0][N-1],gmap[0][N-1]);
    }



//**********************************动规*****************************************************************

    /**
     * 采用缓存方法，解决递归过程中的重复计算问题
     * @param arr
     * @return
     */
    public static int win2(int[] arr){
        //因为涉及到递归的两个过程，所以需要采用两个表来存储状态
        int N = arr.length;
        int[][] fmap = new int[N][N];//在N的数组长度下，可以确保，任何在任何一个位置取卡片，不会右越界的情况
        int[][] gmap = new int[N][N];

        //初始化状态容器
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                //初始化为-1，目的是为-1时，表示没有被计算过
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }

        int p1 = f2(arr,0,N-1,fmap,gmap);//先手拿牌的最得分
        int p2 = g2(arr,0,N-1,fmap,gmap);//后手拿牌的最大的分
        return Math.max(p1,p2);
    }

    /**
     * 传入一个数组和两个状态数组，可以查询先拿牌时获得的最大分数，计算过的数据保存在状态数组中
     * @param arr
     * @param l
     * @param r
     * @param fmap
     * @param gmap
     * @return
     */
    public static int f2(int[] arr,int l,int r,int[][] fmap,int[][] gmap){
        //如果先手拿牌，只有一个元素，那么就直接返回值，并将其保存在状态数组中
        if (l == r){
            fmap[l][r] = arr[l];
            return arr[l];
        }
        //否则至少存在两个元素，l，r是否在先手拿牌中被计算过，计算过过则直接返回计算的结果
        int ans = 0;
        if (fmap[l][r] != -1){
            return fmap[l][r];
        }else {
            //否则没有计算过，
            int p1 = arr[l] + g2(arr,l+1,r,fmap,gmap);
            int p2 = arr[r] + g2(arr,l,r-1,fmap,gmap);
            ans = Math.max(p1,p2);
            //计算完成，将结果保存到状态数组中，以提供给后面的计算使用
            fmap[l][r] = ans;
        }
        return ans;
    }

    /**
     * g2同g1的方法一样
     * @param arr
     * @param l
     * @param r
     * @param fmap
     * @param gmap
     * @return
     */
    public static int g2(int[] arr,int l,int r,int[][] fmap,int[][] gmap){
        if (gmap[l][r] != -1){
            return gmap[l][r];
        }

        int ans = 0;
        if (l != r){
            int p1 = f2(arr,l+1,r,fmap,gmap);
            int p2 = f2(arr,l,r-1,fmap,gmap);
            ans = Math.min(p1,p2);
            gmap[l][r] = ans;
        }
        return ans;
    }

//***********************************递归****************************************************************

    /**
     * 给定一个乱序数组，按照规则就可以获得最大分数
     * @param arr
     * @return
     */
    public static int win1(int[] arr){
        if (arr.length == 0 || arr == null){
            return -1;
        }
        int fir = f1(arr,0,arr.length-1);
        int sec = g1(arr,0,arr.length - 1);
        return Math.max(fir,sec);
    }

    /**
     * 先手拿牌的方法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    public static  int f1(int[] arr, int l, int r){
       //如果只有一张牌，直接返回这张牌的分数
       if (l == r){
           return arr[l];
       }
       //否则至少存在两张牌
        int p1 = arr[l] + g1(arr,l+1,r);
        int p2 = arr[r] + g1(arr,l,r-1);
        return Math.max(p1,p2);
    }

    /**
     * 后手拿牌的方法
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int g1(int[] arr, int l, int r) {
        //如果 l==r ，后手拿牌的人只能获得0分
        if (l == r){
            return 0;
        }
        //否则至少存在两张牌，那么B非常聪明，肯定会选择一种方案，给A获得最小的分数
        int p1 = f1(arr,l+1,r);
        int p2 = f1(arr,l,r-1);
        return Math.min(p1,p2);
    }
}
